package com.caoyanan.algorithm.question.zuoTraining.training004.class04;

import com.caoyanan.algorithm.question.zuoTraining.LogarithmInputGenerator;

import java.util.Arrays;

/**
 * 有序数组求最大K个数
 *
 * 给定两个整数数组A和B
 * A是长度为m、元素从小到大排好序了
 * B是长度为n、元素从小到大排好序了
 * 希望从A和B数组中，找出最大的k个数字
 *
 * @author: caoyanan
 * @time: 2021/6/19 20:13
 */
public class Question01_FindMaxKNumber {

    public static void main(String[] args) {

        //首先解决一个问题，两个同为k长度的数组，求整体第k小的数是多少的算法原型
        int count = 1000000;
        for (int i = 0; i < count; i++) {

            int k = (int) (Math.random() * 10 + 5);
            int[] arr1 = LogarithmInputGenerator.getInstance().generateRandomSortArray(k, 100);
            int[] arr2 = LogarithmInputGenerator.getInstance().generateRandomSortArray(k, 100);
            int answer1 = violence(arr1, arr2);
            int answer2 = dichotomyRecursion(arr1, 0, arr1.length-1, arr2, 0, arr2.length - 1);
            int answer3 = dichotomyLoop(arr1, 0, arr1.length-1, arr2, 0, arr2.length - 1);
            if (answer1 != answer2 || answer2 != answer3) {
                System.out.printf("数组1 %s 数组2 %s, 第 %s 大的数，暴力方法结果为 %s, 二分结果为 %s, 栈二分 %s \n",
                        Arrays.toString(arr1), Arrays.toString(arr2), k, answer1, answer2, answer3);
            }

            int[] arr3 = LogarithmInputGenerator.getInstance().generateRandomSortArray(k + 7, 100);
            int answer4 = violenceDifferentLengthArray(arr1, arr3, k - 2);
            int answer4_1 = violenceDifferentLengthArray(arr1, arr3, k + 2);
            int answer4_2 = violenceDifferentLengthArray(arr1, arr3, k + 9);

            int answer5= dichotomyDifferentLengthArray(arr1, arr3, k - 2);
            int answer5_1 = dichotomyDifferentLengthArray(arr1, arr3, k + 2);
            int answer5_2 = dichotomyDifferentLengthArray(arr1, arr3, k + 9);

            if (answer4 != answer5 || answer4_1 != answer5_1 || answer4_2 != answer5_2) {
                System.out.printf("数组1 %s 数组2 %s, 整体第 %s 大的数 %s %s ，第 %s 大的数 %s %s, 第 %s 大的数 %s %s \n",
                        Arrays.toString(arr1), Arrays.toString(arr3), k-2, answer4, answer5,
                        k+2, answer4_1, answer5_1, k+9, answer4_2, answer5_2);
            }
        }
    }

    /**
     * 二分求两个不同长度有序数组整体第k小的值
     * 时间复杂度 O(log(min(N1, N2)))
     * @param arr1
     * @param arr2
     * @param k
     * @return
     */
    private static int dichotomyDifferentLengthArray(int[] arr1, int[] arr2, int k) {
        int minLength = Math.min(arr1.length, arr2.length);
        int maxLength = Math.max(arr1.length, arr2.length);

        //比小数组长度还短
        if (k <= minLength) {
            return dichotomyLoop(arr1, 0, k - 1, arr2, 0, k - 1);
        }
        //介于小数组长度和大数组长度之间
        // 如 [1, 2, 3 ] 和 [1'，2'，3'，4'，5'，6']  求整体第5小
        // 首先， [1']不可能， [6']不可能  ，即 [1,2,3] 和 [2'，3'，4'，5']求整体第 4小，
        // 手动看一下 [2']是不是第[3]大，如果是，[2']直接就是第5小，如果不是， [1,2,3] 和 [3',4',5'] 求整体第3小
        if (k <= maxLength) {
            if (arr2[k - minLength - 1] >= arr1[minLength - 1]) {
                return arr2[k - minLength - 1];
            }
            return dichotomyLoop(arr1, 0, minLength - 1, arr2, k - minLength, k - 1);
        }

        // 大于大数组长度
        // 如 [1, 2, 3 ] 和 [1'，2'，3'，4'，5'，6']  求整体第8小
        // 首先 [1',2',3',4']不可能，4'最大是第7小，[1]不可能，[2,3]和[5',6'] 求整体第2小， 但是最后总的就是求整体第7小了，并不是整体第8小
        // 手动看一下 [5'] 是否大于 [3],如果是，5'就是整体第8小，否则5'淘汰，
        //  手动看一下 [2]是否大于[6']，如果是，[2]就是整体第8小，否则2'淘汰， [3] 和 [5']求整体第1小，且已经淘汰了7个数，最终就求出整体第8小

        // [k - maxLength - 1, minLength-1]   [k - minLength-1,  maxLength-1] 已经淘汰了 2k - minLength - maxLength - 2个
        if (arr1[k - maxLength - 1] >= arr2[maxLength - 1]) {
            return arr1[k - maxLength - 1];
        }
        if (arr2[k - minLength - 1] >= arr1[minLength - 1]) {
            return arr2[k - minLength - 1];
        }
        return dichotomyLoop(arr1, k - maxLength, minLength - 1, arr2, k - minLength, maxLength - 1);

    }

    /**
     * 暴力方法求两个不同长度有序数组整体求第k小
     * 时间复杂度O(k)
     * @param arr1
     * @param arr2
     * @param k
     * @return
     */
    private static int violenceDifferentLengthArray(int[] arr1, int[] arr2, int k) {

        int a = 0;
        int b = 0;
        for (int i = 0; i < k - 1; i++) {
            if (a >= arr1.length) {
                b ++;
                continue;
            }
            if (b >= arr2.length) {
                a ++;
                continue;
            }
            if (arr1[a] >= arr2[b]) {
                b++;
                continue;
            }
            a ++;
        }
        if (a >= arr1.length) {
            return arr2[b];
        }
        if (b >= arr2.length) {
            return arr1[a];
        }
        return Math.min(arr1[a], arr2[b]);
    }

    /**
     * 使用 循环二分 求 两个k长度有序数组整体第k大的数
     * @param arr1
     * @param arr2
     * @return
     */
    private static int dichotomyLoop(int[] arr1, int from1, int to1, int[] arr2, int from2, int to2) {

        while (from1 != to1) {
            int middle1 = (from1 + to1) / 2;
            int middle2 = (from2 + to2) / 2;
            //是否是偶数
            int even = (to1 - from1 + 1) % 2 == 0 ? 1: 0;

            if (arr1[middle1] == arr2[middle2]) {
                return arr1[middle1];
            }
            if (arr1[middle1] > arr2[middle2]) {
                to1 = middle1;
                from2 = middle2+even;
                continue;
            }
            from1 = middle1 + even;
            to2 = middle2;
        }
        return Math.min(arr1[from1], arr2[from2]);
    }

    /**
     * 递归二分寻找两个k长度大小的数组整体第k大的数
     * @param arr1
     * @param from1
     * @param to1
     * @param arr2
     * @param from2
     * @param to2
     * @return
     */
    private static int dichotomyRecursion(int[] arr1, int from1, int to1, int[] arr2, int from2, int to2) {

        if (from1 == to1) {
            return Math.min(arr1[from1], arr2[from2]);
        }
        int middle1= (from1 + to1) >> 1;
        int middle2 = (from2 + to2) >> 1;
        // 是否是偶数
        int even = ((to1 - from1 + 1) % 2) == 1 ? 0 : 1;
        if (arr1[middle1] == arr2[middle2]) {
            return arr1[middle1];
        }
        if (arr1[middle1] > arr2[middle2]) {
            return dichotomyRecursion(arr1, from1, middle1, arr2, middle2+even, to2);
        }
        return dichotomyRecursion(arr1, middle1+even, to1, arr2, from2, middle2);
    }

    private static int violence(int[] arr1, int[] arr2) {
        int a = 0;
        int b = 0;
        for (int i = 0; i < arr1.length-1; i++) {
            if (arr1[a] >= arr2[b]) {
                b++;
            } else {
                a++;
            }
        }
        if (a > arr1.length - 1) {
            return arr2[b];
        }
        if (b > arr2.length - 1) {
            return arr1[a];
        }
        return Math.min(arr1[a], arr2[b]);
    }
}
